翻訳と辞書 Words near each other ・ King Agron ・ King Ahaz's Seal ・ King Ai of Chu ・ Kinetic logic ・ Kinetic Luna ・ Kinetic military action ・ Kinetic minimum box ・ Kinetic minimum spanning tree ・ Kinetic Monte Carlo ・ Kinetic Monte Carlo surface growth method ・ Kinetic Mountain Goat ・ Kinetic novel ・ Kinetic photography ・ Kinetic Playground ・ Kinetic PreProcessor ・ Kinetic priority queue ・ Kinetic proofreading ・ Kinetic Rain ・ Kinetic Records ・ Kinetic resolution ・ Kinetic Rule Language ・ Kinetic Sand ・ Kinetic scheme ・ Kinetic sculpture race ・ Kinetic Securities ・ Kinetic smallest enclosing disk ・ Kinetic sorted list ・ Kinetic Suspension Technology ・ Kinetic term ・ Kinetic theory Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Kinetic priority queue ： ウィキペディア英語版 Kinetic priority queue A Kinetic Priority Queue is an abstract kinetic data structure. It is a variant of a priority queue designed to maintain the maximum (or minimum) priority element (key-value pair) when the priority of every element is changing as a continuous function of time. Kinetic priority queues have been used as components of several kinetic data structures, as well as to solve some important non-kinetic problems such as the k-set problem and the connected red blue segments intersection problem. == Implementations == The operations supported are: * : create an empty kinetic priority queue * (or find-min): - return the (or for a ) value stored in the queue at the current virtual time . * : - insert a key into the kinetic queue at the current virtual time, whose value changes as a continuous function of time . * - delete a key at the current virtual time . There are several variants of kinetic priority queues, which support the same basic operations but have different performance guarantees. Some of the most common implementations are kinetic heaps which are simple to implement but don't have tight theoretical performance bounds, and their randomized variants - kinetic heaters and kinetic hangers - which are easier to analyze. There is also a heap-like structure based on the dynamic convex hull data structure〔 which achieves better performance for affine motion of the priorities, but doesn't support curved trajectories. The kinetic tournament is another commonly used implementation. It achieves, deterministically, the same performance bounds as the heater or hanger, however it is less local and responsive than the heap-based data-structures. }n) || $O(m\; \backslash alpha(n)\backslash log^2\; n)$ || $O(m\backslash log\; n\; \backslash log\; \backslash log\; n)$ |- | -intersecting curves|| $O(n^2\backslash log\; n)$ || $O(\backslash lambda\_\backslash delta(n)\backslash log\; n)$ || n/a |} Here, $\backslash alpha(x)$ denotes the inverse Ackermann function.$\backslash delta$-intersecting curves refer to curves where each pair has at most $\backslash delta$ intersections, and $\backslash lambda\_\backslash delta(n)$ refers to a term in the Davenport-Schinzel sequence, which gives the maximum size of the upper envelope of $n$ $\backslash delta-$intersecting curves. $n$ is the largest number of elements in the queue at any given time, while $m$ refers to the total number of elements that are ever in the queue. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kinetic priority queue」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.